package day13;

/**
 * n个灯泡排成一行，编号从 1 到n。最初，所有灯泡都关闭。每天只打开一个灯泡，直到n天后所有灯泡都打开。
 *
 * 给你一个长度为n的灯泡数组 blubs ，其中 bulls[i] = x 意味着在第 (i+1) 天，我们会把在位置 x 的灯泡打开，其中 i 从 0 开始，x 从 1 开始。
 *
 * 给你一个整数k，请返回恰好有两个打开的灯泡，且它们中间 正好 有k个全部关闭的 灯泡的 最小的天数 。如果不存在这种情况，返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：
 * bulbs = [1,3,2]，k = 1
 * 输出：2
 * 解释：
 * 第一天 bulbs[0] = 1，打开第一个灯泡 [1,0,0]
 * 第二天 bulbs[1] = 3，打开第三个灯泡 [1,0,1]
 * 第三天 bulbs[2] = 2，打开第二个灯泡 [1,1,1]
 * 返回2，因为在第二天，两个打开的灯泡之间恰好有一个关闭的灯泡。
 * 示例 2：
 *
 * 输入：bulbs = [1,2,3]，k = 1
 * 输出：-1
 *
 *
 */
public class Solution2 {
    public int kEmptySlots(int[] bulbs, int k) {
        int[] days = new int[bulbs.length];
        for (int i = 0; i < bulbs.length; i++) {
            days[bulbs[i] - 1] = i + 1;
        }

        int ans = Integer.MAX_VALUE;
        int left = 0, right = k+1;

        search: while (right < days.length) {
            for (int i = left+1; i < right; ++i) {
                if (days[i] < days[left] || days[i] < days[right]) {
                    left = i;
                    right = i + k + 1;
                    continue search;
                }
            }
            ans = Math.min(ans, Math.max(days[left], days[right]));
            left = right;
            right = left + k + 1;
        }

        return ans < Integer.MAX_VALUE ? ans : -1;
    }
}
